package com.dkd.day20250630;

import com.dkd.day20250614.ListNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class SolutionmergeKLists {
    public static void main(String[] args) {

    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        //使用堆，每次里面都数量都是列表大小的数，每次都弹出最小数
        //1比较器，比较val
        Comparator<ListNode> comparator = Comparator.comparing(o -> o.val);
        //2建立节点
        ListNode head = null;
        ListNode temp = null;

        //构建堆
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(comparator);
        //第一次添加元素
        for(int i = 0; i < lists.size(); i++) {
            if(lists.get(i) != null) {
                heap.offer(lists.get(i));
            }
        }

        while(!heap.isEmpty()) {
            //弹出最小值
            ListNode temp0 = heap.poll();
            //初始化
            if(head == null){
                head = temp0;
                temp =  head;
            }else{//指向下一个，进入下一场循环
                temp.next = temp0;
                temp = temp.next;
            }
            if(temp.next != null) {
                heap.offer(temp.next);
                //heap中扔过去下一个
            }
        }

        //
        return head;
    }
}
